﻿using System;

namespace MaxAreaSumMatrix
{
    class MaxAreaSumMatrix
    {
        static void PrintResult(int[,] matrix, int sum, int startRowIndex, int startColIndex, int length)
        {
            for (int row = startRowIndex, rowLength = startRowIndex + length; row < rowLength; row++)
            {
                for (int col = startColIndex, colLength = startColIndex + length; col < colLength; col++)
                {
                    Console.Write("{0} ", matrix[row, col]);
                }
                Console.WriteLine();
            }
            Console.WriteLine("Sum: {0}", sum);
        }

        static int Sum(int[,] matrix, int rowIndex, int colIndex, int length)
        {
            int sum = 0;
            for (int row = rowIndex, rowLength = rowIndex + length; row < rowLength; row++)
            {
                for (int col = colIndex, colLength = colIndex + length; col < colLength; col++)
                {
                    sum += matrix[row, col];
                }
            }
            return sum;
        }

        static int[] MaxAreaSum(int[,] matrix, int size)
        {
            int bestSum = int.MinValue,
            startRowIndex = 0,
            startColIndex = 0;

            for (int row = 0, rowsLen = matrix.GetLength(0) - size; row <= rowsLen; row++)
            {
                for (int col = 0, colsLen = matrix.GetLength(1) - size; col <= colsLen; col++)
                {
                    int tempSum = Sum(matrix, row, col, size);
                    if (tempSum > bestSum)
                    {
                        startRowIndex = row;
                        startColIndex = col;
                        bestSum = tempSum;
                    }
                }
            }
            return new int[] { bestSum, startRowIndex, startColIndex };
        }
        // o o o o o
        // o o o o o
        // o o o o o
        // o o o o x
        static void Main()
        {
            int rows = 4,//int.Parse(Console.ReadLine());
            cols = 5;
            int[,] matrix = new int[rows, cols];
            matrix[rows - 1, cols - 1] = 1;

            int[] result = MaxAreaSum(matrix, 3);
            PrintResult(matrix, result[0], result[1], result[2], 3);
        }
    }
}
